1056F - Write The Contest - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long double ldb;
const int mxn=105;
int n,m,i,j,t,k,s;
db dp[mxn][mxn*10],c,ti;
struct node
{
db dif;int pt;
}a[mxn];
bool cmp(node x,node y){return x.dif<y.dif;}
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
scanf("%d%lf%lf",&n,&c,&ti);
for (i=1;i<=n;++i) scanf("%lf%d",&a[i].dif,&a[i].pt);
sort(a+1,a+n+1,cmp);
for (j=0;j<=n;++j)
for (i=0;i<=n*10;++i) dp[j][i]=1e18;
s=0;dp[0][0]=0.0;
for (i=1;i<=n;++i)
{
for (k=i-1;k>=0;--k)
for (j=s;j>=0;--j)
dp[k+1][j+a[i].pt]=min(dp[k+1][j+a[i].pt],dp[k][j]*10.0/9.0+a[i].dif*10.0/9.0);
s+=a[i].pt;
}
int ans=0;
for (i=0;i<=n;++i)
for (j=0;j<=s;++j)
{
db tmp;
if (dp[i][j]>=1.0/c) tmp=2.0*sqrt(dp[i][j]/c)-1.0/c;
else tmp=dp[i][j];
if (tmp+i*10.0<=ti) ans=max(ans,j);
}
printf("%d\n",ans);
}
return 0;
}